package mo.offer_special;

import java.util.ArrayList;
import java.util.List;

public class L083 {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        int n = nums.length;
        boolean[] visited = new boolean[n];
        dfs(res, combination, visited, nums, 0);
        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> combination, boolean[] visited, int[] nums, int i) {
        if (i == nums.length) {
            res.add(new ArrayList<>(combination));
        }

        for (int j = 0; j < nums.length; j++) {
            if (!visited[j]) {
                combination.add(nums[j]);
                visited[j] = true;
                dfs(res, combination, visited, nums, i+1);
                combination.remove(combination.size()-1);
                visited[j] = false;

            }
        }
    }

    public static void main(String[] args) {
        L083 test = new L083();
        System.out.println(test.permute(new int[]{1, 2, 3}));
    }

}
